#include "Grammatical.h"

void grammatical::bootGrammatical() {
    dict = {
        {"CompUnit", 1},
        {"Decl", 2},
        {"FuncDef", 3},
        {"MainFuncDef", 4},
        {"ConstDecl", 5},
        {"VarDecl", 6},
        {"FuncType", 7},
        {"Ident", 8},
        {"FuncFParams", 9},
        {"Block", 10},
        {"BType", 11},
        {"VarDef", 12},
        {"FuncFParam", 13},
        {"BlockItem", 14},
        {"ConstExp", 15},
        {"InitVal", 16},
        {"Stmt", 17},
        {"AddExp", 18},
        {"Exp", 19},
        {"LVal", 20},
        {"Cond", 21},
        {"FormatString", 22},
        {"MulExp", 23},
        {"LOrExp", 24},
        {"LAndExp", 25},
        {"EqExp", 26},
        {"UnaryExp", 27},
        {"RelExp", 28},
        {"PrimaryExp", 32},
        {"FuncRParams", 33},
        {"Number", 34},
        {"IntConst", 35},
        {"decimal-const", 36},
        {"nonzero-digit", 37},
        {"UnaryOp", 38},
        {"ConstInitVal", 39},
        {"ConstDef", 40},
        {"main", 41},
        {"const", 42},
        {"int", 43},
        {"break", 44},
        {"continue", 45},
        {"if", 46},
        {"else", 47},
        {"!", 48},
        {"&&", 49},
        {"||", 50},
        {"while", 51},
        {"getint", 52},
        {"printf", 53},
        {"return", 54},
        {"+", 55},
        {"-", 56},
        {"void", 57},
        {"*", 58},
        {"/", 59},
        {"%", 60},
        {"<", 61},
        {"<=", 62},
        {">", 63},
        {">=", 64},
        {"==", 65},
        {"!=", 66},
        {"=", 67},
        {";", 68},
        {",", 69},
        {"(", 70},
        {")", 71},
        {"[", 72},
        {"]", 73},
        {"{", 74},
        {"}", 75},
		{"AddExpS", 100},
        {"MulExpS", 101},
		{"LOrExpS", 102},
		{"LAndExpS", 103},
		{"EqExpS", 104},
		{"RelExpS", 105},
    };
	str = {" ", "main", "const", "int", "break", "continue", "if", "else", "!", "&&", "||", "while", "getint", "printf", "return",
					  "+", "-", "void", "*", "/", "%", "<", "<=", ">", ">=", "==", "!=", "=", ";", ",", "(", ")", "[", "]", "{", "}"};
}

void grammatical::rollback(int size)
{
	while (output.size() > size)
		output.pop_back();
}


pair<int, bool> grammatical::tryMatch(string type, int position, int size) {
    auto newposition = matchType(dict[type], position);
    if (!newposition.second) {
        rollback(size);
        return {position, false};
    }
    return newposition;
}

pair<int, bool> grammatical::matchMultiple(string type, int position) {
    auto newposition = matchType(dict[type], position);
    while (newposition.second) {
        position = newposition.first;
        newposition = matchType(dict[type], position);
    }
    return {position, true};
}

pair<int, bool> grammatical::matchType(int type, int position)
{
	if (position == words.size())
		return {position, true};
	pair<int, bool> original_pos = {position, false};
	pair<int, bool> newposition;
	int size = output.size();
	switch (type)
	{
	case 1: // CompUnit ::= {Decl} {FuncDef} MainFuncDef
		newposition = matchMultiple("Decl", position);
		position = newposition.first;

		newposition = matchMultiple("FuncDef", position);
		position = newposition.first;

		newposition = tryMatch("MainFuncDef", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;
		output.push_back({"CompUnit", ""});
		return {position, true};
		break;
	case 2: // Decl
		newposition = matchType(dict["ConstDecl"], position);
		if (newposition.second)
			return newposition;

		newposition = matchType(dict["VarDecl"], position);
		if (newposition.second)
			return newposition;

		rollback(size);
		return original_pos;
		break;
	case 3: // FuncDef
		newposition = tryMatch("FuncType", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("Ident", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("(", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		position = matchType(dict["FuncFParams"], position).first;

		newposition = tryMatch(")", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("Block", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"FuncDef", ""});
		return {position, true};
		break;
	case 4: // MainFuncDef
		newposition = tryMatch("int", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("main", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("(", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch(")", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("Block", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"MainFuncDef", ""});
		return {position, true};
		break;
	case 5: // ConstDecl
		newposition = tryMatch("const", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("BType", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("ConstDef", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		do {
			newposition = matchType(dict[","], position);
			if (!newposition.second) {
				break;
			}
			position = newposition.first;

			newposition = tryMatch("ConstDef", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
		} while (true);

		newposition = tryMatch(";", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"ConstDecl", ""});
		return {position, true};
		break;
	case 6: // VarDecl
		newposition = tryMatch("BType", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("VarDef", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		do {
			newposition = matchType(dict[","], position);
			if (!newposition.second) {
				break;
			}
			position = newposition.first;

			newposition = tryMatch("VarDef", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
		} while (true);
		newposition = tryMatch(";", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"VarDecl", ""});
		return {position, true};
		break;
    case 7: // FuncType
        for (const auto& type : {"void", "int", "float"}) {
            newposition = matchType(dict[type], position);
            if (newposition.second) {
                output.push_back({"FuncType", ""});
                return newposition;
            }
        }
        rollback(size);
        return original_pos;
        break;
	case 8: // Ident
		if (words[position].first == "IDENFR")
		{
			output.push_back(words[position]);
			return {position + 1, true};
		}
		rollback(size);
		return original_pos;
		break;
	case 9: // FuncFParams
		newposition = tryMatch("FuncFParam", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		do {
			newposition = matchType(dict[","], position);
			if (!newposition.second) {
				break;
			}
			position = newposition.first;

			newposition = tryMatch("FuncFParam", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
		} while (true);
		output.push_back({"FuncFParams", ""});
		return {position, true};
		break;
	case 10: // Block
		newposition = tryMatch("{", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = matchMultiple("BlockItem", position);
		position = newposition.first;

		newposition = tryMatch("}", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"Block", ""});

		return {position, true};
		break;
	case 11: // BType
		newposition = matchType(dict["int"], position);
		if (newposition.second)
			return newposition;

		newposition = matchType(dict["float"], position);
		if (newposition.second)
			return newposition;

		rollback(size);
		return original_pos;
		break;
	case 12: // VarDef
		newposition = tryMatch("Ident", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		do {
			newposition = matchType(dict["["], position);
			if (!newposition.second) {
				break;
			}
			position = newposition.first;

			newposition = tryMatch("ConstExp", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch("]", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
		} while (true);

		newposition = matchType(dict["="], position);
		if (!newposition.second)
		{
			output.push_back({"VarDef", ""});
			return {position, true};
		}
		position = newposition.first;
		newposition = tryMatch("InitVal", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"VarDef", ""});
		return {position, true};
		break;
	case 13: // FuncFParam
		newposition = tryMatch("BType", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("Ident", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = matchType(dict["["], position);
		if (!newposition.second)
		{
			output.push_back({"FuncFParam", ""});
			return {position, true};
		}
		position = newposition.first;

		newposition = tryMatch("]", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		do {
			newposition = matchType(dict["["], position);
			if (!newposition.second) {
				break;
			}
			position = newposition.first;

			newposition = tryMatch("ConstExp", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch("]", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
		} while (true);

		output.push_back({"FuncFParam", ""});
		return {position, true};
		break;
	case 14: // BlockItem
		newposition = matchType(dict["Decl"], position);
		if (newposition.second)
			return newposition;

		newposition = matchType(dict["Stmt"], position);
		if (newposition.second)
			return newposition;

		rollback(size);
		return original_pos;
		break;
	case 15: // ConstExp
		newposition = tryMatch("AddExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"ConstExp", ""});
		return {position, true};
		break;
	case 16: // InitVal
		newposition = matchType(dict["Exp"], position);
		if (newposition.second)
		{
			output.push_back({"InitVal", ""});
			return newposition;
		}

		newposition = tryMatch("{", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = matchType(dict["InitVal"], position);
		if (newposition.second)
		{
			position = newposition.first;
			do {
				newposition = matchType(dict[","], position);
				if (!newposition.second) {
					break;
				}
				position = newposition.first;

				newposition = tryMatch("InitVal", position, size);
				if (!newposition.second) {
					return newposition;
				}
				position = newposition.first;
			} while (true);
		}
		newposition = tryMatch("}", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"InitVal", ""});
		return {position, true};
		break;
	case 17: // Stmt
		newposition = matchType(dict["LVal"], position);
		if (newposition.second)
		{
			position = newposition.first;
			newposition = matchType(dict["="], position);
			if (newposition.second)
			{
				position = newposition.first;

				newposition = matchType(dict["Exp"], position);
				if (newposition.second)
				{
					position = newposition.first;

					newposition = tryMatch(";", position, size);
					if (!newposition.second) {
						return newposition;
					}
					position = newposition.first;

					output.push_back({"Stmt", ""});
					return {position, true};
				}
				newposition = tryMatch("getint", position, size);
				if (!newposition.second) {
					return newposition;
				}
				position = newposition.first;

				newposition = tryMatch("(", position, size);
				if (!newposition.second) {
					return newposition;
				}
				position = newposition.first;

				newposition = tryMatch(")", position, size);
				if (!newposition.second) {
					return newposition;
				}
				position = newposition.first;

				newposition = tryMatch(";", position, size);
				if (!newposition.second) {
					return newposition;
				}
				position = newposition.first;

				output.push_back({"Stmt", ""});
				return {position, true};
			}
		}
		position = original_pos.first;
		rollback(size);
		newposition = matchType(dict["Block"], position);
		if (newposition.second)
		{
			output.push_back({"Stmt", ""});
			return newposition;
		}
		newposition = matchType(dict["if"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = tryMatch("(", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch("Cond", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch(")", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch("Stmt", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = matchType(dict["else"], position);
			if (newposition.second)
			{
				position = newposition.first;
				newposition = tryMatch("Stmt", position, size);
				if (!newposition.second) {
					return newposition;
				}
				position = newposition.first;
				output.push_back({"Stmt", ""});
				return {position, true};
			}
			else
			{
				output.push_back({"Stmt", ""});
				return {position, true};
			}
		}
		newposition = matchType(dict["while"], position);
		if (newposition.second)
		{
			position = newposition.first;
			newposition = tryMatch("(", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch("Cond", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch(")", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch("Stmt", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
			output.push_back({"Stmt", ""});
			return {position, true};
		}
		newposition = matchType(dict["break"], position);
		if (newposition.second)
		{
			position = newposition.first;
			newposition = tryMatch(";", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
			output.push_back({"Stmt", ""});
			return {position, true};
		}
		newposition = matchType(dict["continue"], position);
		if (newposition.second)
		{
			position = newposition.first;
			newposition = tryMatch(";", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
			output.push_back({"Stmt", ""});
			return {position, true};
		}
		newposition = matchType(dict["return"], position);
		if (newposition.second)
		{
			position = newposition.first;

			position = matchType(dict["Exp"], position).first;

			newposition = tryMatch(";", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
			output.push_back({"Stmt", ""});
			return {position, true};
		}
		newposition = matchType(dict["printf"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = tryMatch("(", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch("FormatString", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			do {
				newposition = matchType(dict[","], position);
				if (!newposition.second) {
					break;
				}
				position = newposition.first;

				newposition = tryMatch("Exp", position, size);
				if (!newposition.second) {
					return newposition;
				}
				position = newposition.first;
			} while (true);

			newposition = tryMatch(")", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch(";", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
			output.push_back({"Stmt", ""});
			return {position, true};
		}
		position = matchType(dict["Exp"], position).first;

		newposition = tryMatch(";", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"Stmt", ""});
		return {position, true};
		break;

	// AddExp->MulExp AddExpS
	// AddExpS->('+'|'-')MulExp AddExpS | e
	case 18: // AddExp
		newposition = tryMatch("MulExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("AddExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"AddExp", ""});
		return {position, true};
		break;
	case 100: // AddExpS
		output.push_back({"AddExp", ""});
		if (matchType(dict["+"], position).second)
			position++;
		else if (matchType(dict["-"], position).second)
			position++;
		else
		{
			output.pop_back();
			return {position, true};
		}

		newposition = tryMatch("MulExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("AddExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		return {position, true};
		break;
	case 19: // Exp
		newposition = tryMatch("AddExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"Exp", ""});
		return {position, true};
		break;
	case 20: // LVal
		newposition = tryMatch("Ident", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		do {
			newposition = matchType(dict["["], position);
			if (!newposition.second) {
				break;
			}
			position = newposition.first;

			newposition = tryMatch("Exp", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch("]", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
		} while (true);
		output.push_back({"LVal", ""});
		return {position, true};
		break;
	case 21: // Cond
		newposition = tryMatch("LOrExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"Cond", ""});
		return {position, true};
		break;
	case 22: // FormatString
		if (words[position].first == "STRCON")
		{
			output.push_back(words[position]);
			return {position + 1, true};
		}
		else
			return {position, false};
		break;

	// MulExp->UnaryExp MulExpS
	// MulExpS->('*'|'/'|'%')UnaryExp MulExpS | e
	case 23: // MulExp
		newposition = tryMatch("UnaryExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("MulExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"MulExp", ""});
		return {position, true};
		break;
    case 101: // MulExpS
        output.push_back({"MulExp", ""});
        for (const auto& op : {"*", "/", "%"}) {
            if (matchType(dict[op], position).second) {
                position++;
                break;
            }
        }
        if (output.back().first == "MulExp" && output.back().second.empty()) {
            output.pop_back();
            return {position, true};
        }

        newposition = tryMatch("UnaryExp", position, size);
        if (!newposition.second) {
            return newposition;
        }
        position = newposition.first;

        newposition = tryMatch("MulExpS", position, size);
        if (!newposition.second) {
            return newposition;
        }
        position = newposition.first;

        return {position, true};
        break;
	// LOrExp->LAndExp LOrExpS
	// LOrExpS->'||'LAndExp LOrExpS | e
	case 24: // LOrExp
		newposition = tryMatch("LAndExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("LOrExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"LOrExp", ""});
		return {position, true};
		break;
	case 102: // LOrExps
		output.push_back({"LOrExp", ""});
		newposition = matchType(dict["||"], position);
		if (!newposition.second)
		{
			output.pop_back();
			return {position, true};
		}
		position = newposition.first;

		newposition = tryMatch("LAndExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("LOrExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		return {position, true};
		break;

	// LAndExp->EqExp LAndExpS
	// LAndExpS->'&&'EqExp LAndExpS | e
	case 25: // LAndExp
		newposition = tryMatch("EqExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("LAndExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"LAndExp", ""});
		return {position, true};
		break;
	case 103: // LAndExpS
		output.push_back({"LAndExp", ""});
		newposition = matchType(dict["&&"], position);
		if (!newposition.second)
		{
			output.pop_back();
			return {position, true};
		}
		position = newposition.first;

		newposition = tryMatch("EqExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("LAndExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		return {position, true};
		break;

	// EqExp->RelExp EqExpS
	// EqExpS->('=='|'!=')RelExp EqExpS | e
	case 26: // EqExp
		newposition = tryMatch("RelExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("EqExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"EqExp", ""});
		return {position, true};
		break;
	case 104: // EqExpS
		output.push_back({"EqExp", ""});
		if (matchType(dict["=="], position).second)
			position++;
		else if (matchType(dict["!="], position).second)
			position++;
		else
		{
			output.pop_back();
			return {position, true};
		}

		newposition = tryMatch("RelExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("EqExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		return {position, true};
		break;
	case 27: // UnaryExp

		newposition = matchType(dict["UnaryOp"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = tryMatch("UnaryExp", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			output.push_back({"UnaryExp", ""});
			return {position, true};
		}

		newposition = matchType(dict["Ident"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["("], position);
			if (newposition.second)
			{
				position = newposition.first;

				position = matchType(dict["FuncRParams"], position).first;

				newposition = tryMatch(")", position, size);
				if (!newposition.second) {
					return newposition;
				}
				position = newposition.first;
				output.push_back({"UnaryExp", ""});
				return {position, true};
			}
		}

		position = original_pos.first;
		rollback(size);
		newposition = matchType(dict["PrimaryExp"], position);
		if (newposition.second)
		{
			output.push_back({"UnaryExp", ""});
			return newposition;
		}
		else
		{
			rollback(size);
			return original_pos;
		}
		break;

	// RelExp->AddExp RelExpS
	// RelExpS->('<'|'>'|'<='|'>=')AddExp RelExpS | e
	case 28: // RelExp
		newposition = tryMatch("AddExp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("RelExpS", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"RelExp", ""});
		return {position, true};
		break;
    case 105: // RelExps
        output.push_back({"RelExp", ""});
        for (const auto& op : {"<", ">", "<=", ">="}) {
            if (matchType(dict[op], position).second) {
                position++;
                break;
            }
        }
        if (output.back().first == "RelExp" && output.back().second.empty()) {
            output.pop_back();
            return {position, true};
        }

        newposition = tryMatch("AddExp", position, size);
        if (!newposition.second) {
            return newposition;
        }
        position = newposition.first;

        newposition = tryMatch("RelExpS", position, size);
        if (!newposition.second) {
            return newposition;
        }
        position = newposition.first;

        return {position, true};
        break;
	case 32: // PrimaryExp
		newposition = matchType(dict["Number"], position);
		if (newposition.second)
		{
			output.push_back({"PrimaryExp", ""});
			return newposition;
		}

		newposition = matchType(dict["LVal"], position);
		if (newposition.second)
		{
			output.push_back({"PrimaryExp", ""});
			return newposition;
		}

		newposition = tryMatch("(", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch("Exp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = tryMatch(")", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"PrimaryExp", ""});
		return {position, true};
		break;
	case 33: // FuncRParams
		newposition = tryMatch("Exp", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		do {
			newposition = matchType(dict[","], position);
			if (!newposition.second) {
				break;
			}
			position = newposition.first;

			newposition = tryMatch("Exp", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
		} while (true);
		output.push_back({"FuncRParams", ""});
		return {position, true};
		break;
    case 34: // Number
        newposition = tryMatch("IntConst", position, size);
        return newposition.second ? (position = newposition.first, output.push_back({"Number", ""}), std::make_pair(position, true)) : newposition;
        break;
    case 35: // IntConst
        return (words[position].first == "INTCON") ? (output.push_back(words[position]), std::make_pair(position + 1, true)) : std::make_pair(position, false);
        break;
	case 36: // decimal-const
	case 37: // nonzero-digit
    case 38: // UnaryOp
        for (const auto& op : {"+", "-", "!"}) {
            if (matchType(dict[op], position).second) {
                position++;
                break;
            }
        }
        if (position == original_pos.first) {
            rollback(size);
            return original_pos;
        }
        output.push_back({"UnaryOp", ""});
        return {position, true};
        break;
	case 39: // ConstInitVal
		newposition = matchType(dict["ConstExp"], position);
		if (newposition.second)
		{
			output.push_back({"ConstInitVal", ""});
			return newposition;
		}

		newposition = tryMatch("{", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		newposition = matchType(dict["ConstInitVal"], position);
		if (newposition.second)
		{
			position = newposition.first;
			do {
				newposition = matchType(dict[","], position);
				if (!newposition.second) {
					break;
				}
				position = newposition.first;

				newposition = tryMatch("ConstInitVal", position, size);
				if (!newposition.second) {
					return newposition;
				}
				position = newposition.first;
			} while (true);
		}

		newposition = tryMatch("}", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"ConstInitVal", ""});
		return {position, true};
		break;
	case 40: // ConstDef
		newposition = tryMatch("Ident", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		do {
			newposition = matchType(dict["["], position);
			if (!newposition.second) {
				break;
			}
			position = newposition.first;

			newposition = tryMatch("ConstExp", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;

			newposition = tryMatch("]", position, size);
			if (!newposition.second) {
				return newposition;
			}
			position = newposition.first;
		} while (true);
		newposition = matchType(dict["="], position);
		if (!newposition.second)
		{
			output.push_back({"ConstDef", ""});
			return {position, true};
		}
		position = newposition.first;

		newposition = tryMatch("ConstInitVal", position, size);
		if (!newposition.second) {
			return newposition;
		}
		position = newposition.first;

		output.push_back({"ConstDef", ""});
		return {position, true};
		break;
    default:
        return (words[position].second == str[type - 40]) ? 
            (output.push_back(words[position]), make_pair(position + 1, true)) : 
            make_pair(position, false);
        break;
	}
}

vector<pair<string, string>> grammatical::resolve(vector<pair<string, string>> context)
{
    output.clear();
    words = move(context);
    auto position = matchType(dict["CompUnit"], 0).first;
    return output;
}